package com.lw.leetcode.back.b;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * back
 * 93. 复原 IP 地址
 * 剑指 Offer II 087. 复原 IP
 *
 * @Author liw
 * @Date 2021/7/2 13:53
 * @Version 1.0
 */
public class RestoreIpAddresses {

    public static void main(String[] args) {
        RestoreIpAddresses test = new RestoreIpAddresses();
        // ["1.92.168.11","19.2.168.11","19.21.68.11","19.216.8.11","19.216.81.1","192.1.68.11","192.16.8.11","192.16.81.1","192.168.1.1"]
//        String str = "19216811";
//        String str = "1231231231234";
        // ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
//        String str = "101023";
        // ["0.10.0.10","0.100.1.0"]
//        String str = "010010";
        String str = "0000";
        List<String> strings = test.restoreIpAddresses(str);
        System.out.println(strings);
    }


    private int[] arr;
    private String s;
    private int length;
    private List<String> list;
    private String format = "%s.%s.%s.%s";

    public List<String> restoreIpAddresses(String s) {
        length = s.length();
        if (length > 12) {
            return Collections.emptyList();
        }
        arr = new int[4];
        this.s = s;
        list = new ArrayList<>();
        find(0, 0);
        return list;
    }

    private void find(int index, int n) {
        if (n == 3) {
            String str = s.substring(index);
            if (str.length() > 3) {
                return;
            }
            if (str.startsWith("0")) {
                if (str.length() == 1) {
                    arr[n] = 0;
                    list.add(String.format(format, arr[0], arr[1], arr[2], arr[3]));
                }
            } else {
                int value = Integer.parseInt(str);
                if (value <= 255 && value > 0) {
                    arr[n] = value;
                    list.add(String.format(format, arr[0], arr[1], arr[2], arr[3]));
                }

            }
        } else {
            for (int i = index + 1; i <= length - 3 + n && i <= index + 3; i++) {
                String str = s.substring(index, i);
                if (str.startsWith("0")) {
                    if (str.length() == 1) {
                        arr[n] = 0;
                        find(i, n + 1);
                    }
                } else {
                    int value = Integer.parseInt(str);
                    if (value <= 255 && value > 0) {
                        arr[n] = value;
                        find(i, n + 1);
                    }
                }
            }
        }
    }

}
